! Queue in Fortran
module queue_m

    implicit none
    private

    public :: queue_t

    type node_t
        private
        type(node_t), pointer :: next => null()
        class(*), allocatable :: item !! content of the node
    contains
        procedure :: clear => node_t_clear
    end type node_t

    type queue_t
        private
        integer :: num_nodes = 0 !! number of nodes in the queue
        type(node_t), pointer :: head => null() !! head of the queue
        type(node_t), pointer :: tail => null() !! tail of the queue
    contains
        procedure :: enqueue => queue_t_enqueue
        procedure :: dequeue => queue_t_dequeue
        procedure :: size => queue_t_size
        procedure :: clear => queue_t_clear
    end type queue_t

contains

    !> Initialize the node from a new item
    pure function init_node(new_item) result(new_node)
        class(*), intent(in) :: new_item
        type(node_t) new_node
        allocate (new_node%item, source=new_item)
    end function init_node

    !> Clear the node
    pure subroutine node_t_clear(self)
        class(node_t), intent(inout) :: self
        if (allocated(self%item)) deallocate (self%item)
        nullify (self%next)
    end subroutine node_t_clear

    !> Enqueue an item to the queue
    pure subroutine queue_t_enqueue(self, item)
        class(queue_t), intent(inout) :: self
        class(*), intent(in) :: item
        if (associated(self%tail)) then
            allocate (self%tail%next, source=init_node(item))
            self%tail => self%tail%next
        else
            allocate (self%head, source=init_node(item))
            self%tail => self%head
        end if
        self%num_nodes = self%num_nodes + 1
    end subroutine queue_t_enqueue

    !> Dequeue an item from the queue
    impure subroutine queue_t_dequeue(self, item)
        class(queue_t), intent(inout) :: self
        class(*), intent(out), allocatable, optional :: item
        type(node_t), pointer :: curr_node
        if (associated(self%head)) then
            if (present(item)) then
                call move_alloc(self%head%item, item)
            else
                deallocate (self%head%item)
            end if
            curr_node => self%head
            self%head => self%head%next
            self%num_nodes = self%num_nodes - 1
            nullify (curr_node%next)
            deallocate (curr_node)
            if (self%num_nodes == 0) then
                nullify (self%head, self%tail)
            end if
        end if
    end subroutine queue_t_dequeue

    !> Get the size of the queue
    pure integer function queue_t_size(self) result(size)
        class(queue_t), intent(in) :: self
        size = self%num_nodes
    end function queue_t_size

    !> Clear the queue
    pure subroutine queue_t_clear(self)
        class(queue_t), intent(inout) :: self
        type(node_t), pointer :: curr_node
        do while (self%num_nodes > 0)
            curr_node => self%head
            if (associated(curr_node%next)) self%head => self%head%next
            call curr_node%clear()
            deallocate (curr_node)
            self%num_nodes = self%num_nodes - 1
        end do
        nullify (self%head, self%tail)
    end subroutine queue_t_clear

end module queue_m

